package com.cy.tree;

/**
 * @Author: cy
 * @Date: 2021/09/27/19:42
 * @Description:
 */


import java.util.LinkedList;
import java.util.Queue;

/**
 * 完成二叉树的宽度优先遍历也就是层次遍历(如：求一课二叉树的宽度)
 *
 * 方法一：利用队列
 * 1、头节点进队
 * 2、节点出队并输出，输出节点命名为cur
 * 3、如果cur左节点存在，则左节点入队，如果cur右节点存在，则右节点入队 (先左后右)
 * 4、周而复始2-3步骤
 */
public class Demo3 {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        System.out.println("层次遍历顺序是:");
        widthOrder(node1);

    }

    //宽度优先遍历
    public static void widthOrder(Node head){
        if(head != null){
            LinkedList<Node> linkedList = new LinkedList<>();
            linkedList.add(head);   //头节点入队
            while (!linkedList.isEmpty()){
                Node cur = linkedList.poll();    //队头元素出队
                System.out.print(cur.value+" ");
                if(cur.left != null){   //假如出队元素有左节点  左节点进队
                    linkedList.add(cur.left);
                }
                if(cur.right != null){  //假如出队元素有右节点  右节点进队
                    linkedList.add(cur.right);
                }
            }
        }else{
            return;
        }
    }

}
